package com.nine.algorithm.recursion.hanoitower;

import java.util.LinkedList;

/**
 * @author nine
 * @version 1.0
 * @description 汉罗塔
 * @date 24/5/3 9:28
 */
public class HanoiTower {

	static LinkedList<Integer> a = new LinkedList<>();
	static LinkedList<Integer> b = new LinkedList<>();
	static LinkedList<Integer> c = new LinkedList<>();

	// 3 2 1
	static void init(int n) {
		for (int i = n; i > 0; i--) {
			a.addLast(i);
		}
	}

	/**
	 * 借用知乎文章，可以更容易看懂：https://zhuanlan.zhihu.com/p/115644459
	 *
	 * @param n 圆盘个数
	 * @param a 源
	 * @param b 借
	 * @param c 目标
	 */
	static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {
		if (n == 0) {
			return;
		}
		// 1. 把 n-1 个盘子【作为一个整体，递归实现】由a，借c，移至b
		move(n - 1, a, c, b);
		// 2. 将最后一个盘子由 a 移至 c
		c.addLast(a.removeLast());
		print();
		// 3. 把 n-1 个盘子【作为一个整体，递归实现】由b，借a，移至c【此时c的最下面是由一个最大的盘子的】
		move(n - 1, b, a, c);
	}

	public static void main(String[] args) {
		init(3);
		print();

		move(3, a, b, c);
		// b.addLast(a.removeLast());
		// print();
	}

	private static void print() {
		System.out.println("----------------------------");
		System.out.println("a = " + a);
		System.out.println("b = " + b);
		System.out.println("c = " + c);
	}


}
